#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n;
int sum[105];
int dp[105][105];
const int INF=0x3f3f3f3f;
int main(){
	//第一种石子合并是任何两堆合并，使用优先队列解决
	//第二种石子合并是链式的，相邻两堆的合并
    while(scanf("%d",&n)!=EOF){
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        int x;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            sum[i]=sum[i-1]+x;
        }
	    //len表示区间的长度 比如左端点i=1 len=2那么右端点就是1+2-1=2 区间长度就为2
        for(int len=2;len<=n;len++){
		   //i为左端点 i+len-1就是右端点 不能越界
            for(int i=1;i+len-1<=n;i++){
			    //初始化为INF 保证min函数起作用
			    //因为要更新的就是这个区间的值
                dp[i][i+len-1]=INF;
			    //k表示区间截断的点
			    //从左端点到右端点依次枚举
                for(int k=i;k<=i+len-1;k++){
                    dp[i][i+len-1]=min(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]+sum[i+len-1]-sum[i-1]);
                }
            }
        }
        printf("%d\n",dp[1][n]);
    }
    return 0;
}
